# 初始状态和目标状态
import copy
import time

initial = [
    [5, 1, 2, 4],
    [9, 6, 3, 8],
    [13, 15, 10, 11],
    [14, 0, 7, 12]
]
goal = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 0]
]
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def find_0(state):  # 返回0即空格的位置
    for i in state:
        for j in i:
            if j == 0:
                return state.index(i), i.index(j)


def print_state(state):  # 可视化输出
    for i in state:
        print(f'{i[0]}\t{i[1]}\t{i[2]}\t{i[3]}')
    print()


visited = []  # 放置已经访问过的方块
min_length = 100000
min_path = []
step = 0  # 试探的总步数
path = []


def DFS(state, depth):
    global min_length, min_path, step
    visited.append(state)  # 将当前状态置为已访问，并加入path中,试探步数+1
    path.append(state)
    step = step + 1
    if depth > 15:  # 如果递归深度太大，则舍弃
        return
    if state == goal:  # 如果到达目标状态，当前可行路径长度与最短长度比较
        if min_length > len(path):  # 如果更小，更新最短路径和最短路径长度
            min_path.clear()
            min_path = path.copy()
            min_length = len(path)
        return
    cx, cy = find_0(state)  # 找到0的位置(在嵌套列表中的索引)
    for dir in dirs:  # 向四个方向探索
        tx = cx + dir[0]
        ty = cy + dir[1]
        if 0 <= tx < 4 and 0 <= ty < 4:  # 移动后是否出界
            tmp = copy.deepcopy(state)  # 需要这么拷贝!
            tmp[tx][ty], tmp[cx][cy] = tmp[cx][cy], tmp[tx][ty]  # 与0交换位置，得到新的状态
            if tmp not in visited:  # 移动后的状态是否扩展过，如果没有，向下递归
                DFS(tmp, depth + 1)
                visited.remove(tmp)  # 回溯
                path.pop()


start_time = time.perf_counter()
DFS(initial, 0)
print(f'DFS 求解十五数码, 得到最短路径(递归深度设置为15): ')
for i in min_path:
    if i != goal:
        print_state(i)
        print('↓')
print_state(goal)
end_time = time.perf_counter()
runtime = end_time - start_time
print(f'长度为 {min_length - 1}, 总试探步数 {step}, 运行时间 {runtime}')
